public class ShellSort {

/*    shellSort 方法：
    希尔排序是插入排序的改进版本，通过引入“间隔”（gap）来分组排序。
    初始间隔为数组长度的一半，逐步缩小间隔，直到间隔为 1。
    对每个间隔分组进行插入排序。*/
    public static void shellSort(int[] arr){
        int len = arr.length;
        // 初始步长（step）为数组长度的一半，逐步缩小间隔
        for (int step = len / 2; step > 0; step /= 2) {
            // 对每个间隔进行插入排序
            for (int i = step; i < len; i++) {
                int temp = arr[i]; // 当前需要插入的元素
                int j;
                // 将比 temp 大的元素向后移动
                for (j = i; j>= step && arr[j - step]> temp;j -= step){
                    arr[j] = arr[j - step];
                }
                arr[j] = temp;
            }
        }
    }
    // 打印数组
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {12, 34, 54, 2, 3};
        System.out.println("排序前的数组:");
        printArray(arr);

        shellSort(arr);

        System.out.println("排序后的数组:");
        printArray(arr);
    }
}
